// Implement with help from Wikipedia: http://en.wikipedia.org/wiki/Disjoint-set_data_structure
// With help from Emil Stefanov @http://www.emilstefanov.net/Projects/DisjointSets.aspx

#include "DisjointSets.h"


DisjointSets::DisjointSets()
{
	m_numElements = 0;
	m_numSets = 0;
}

DisjointSets::~DisjointSets()
{
	for(int i = 0; i < m_numElements; ++i)
		delete m_nodes[i];
	m_nodes.clear();
	m_numElements = 0;
	m_numSets = 0;
}

// Find the root of the room
int DisjointSets::findSet(Triangle * room) const
{
	MazeNode* currNode = m_nodes[0];

	// Find the root element that represents the set which `elementId` belongs to

        // We find the MazeNode containing the Triangle room
        // *** Will give error if the room does not exist!!
        // *** DO NOT TRY TO FIND A NON-EXISTING ROOM!!!!!!
        int i = 0;
        while( currNode->room != room ) {

            currNode = m_nodes[i];
            i++;
        }

        // So we remember where our desired room is. The int j is the position
        // of that room in our vector
        //int j = i-1;

	while(currNode->parent != NULL)
		currNode = currNode->parent;

	MazeNode* root = currNode;

        // Optimize the tree - Set all the nodes we encountered so that the parent is
        // the root of the new tree. This makes the future calls to findSet faster

	while(currNode != root)
	{
		MazeNode* next = currNode->parent;
		currNode->parent = root;
		currNode = next;
	}

	return root->index;
}

void DisjointSets::unionSets(Triangle * room1, Triangle * room2)
{
        // May or may not need this, but just in case
        // Checks whether or not they're already in the same set
	if(findSet(room1) == findSet(room2))
		return;

	MazeNode* set1 = m_nodes[findSet(room1)];
	MazeNode* set2 = m_nodes[findSet(room2)];

	// Determine which node representing a set has a higher rank. The node with the higher rank is
	// likely to have a bigger subtree so in order to better balance the tree representing the
	// union, the node with the higher rank is made the parent of the one with the lower rank and
	// not the other way around.
	if(set1->rank > set2->rank)
		set2->parent = set1;
	else if(set1->rank < set2->rank)
		set1->parent = set2;
	else // set1->rank == set2->rank
	{
		set2->parent = set1;
		++(set1->rank); // update rank
	}

	// Since two sets have fused into one, there is now one less set so update the set count.
	m_numSets--;
}

void DisjointSets::addElement(Triangle * room)
{
        MazeNode* newNode = new MazeNode();
        newNode->parent = NULL;
        newNode->index = m_nodes.size();
        newNode->rank = 0;
        newNode->room = room;

	m_nodes.push_back(newNode);

	// update element and set counts
	m_numElements++;
	m_numSets++;
}

int DisjointSets::numElements() const
{
	return m_numElements;
}

int DisjointSets::numSets() const
{
	return m_numSets;
}
